Android's Touch Resampling Algorithm
/After digging through the internet and some advice from Jerry Shih, I looked into Google Android's touch resampling algorithm. For those interested, it is located here. Android's touch resampling algorithm is amazing and hats off to the Googler who figured it out. Android uses a combination of touch extrapolation and touch interpolation. Touch interpolation means we take two touch events and create a single touch event somewhere in the middle of the two touch events. Touch extrapolation means we take two touch events and create a single touch event somewhere ahead of the last touch event or predict where a touch event will be. Let's take a look at our standard input from both the LCD refresh display rate of 60 hz and the touchscreen refresh scan rate of 100 hz. (For those who need catching up, please read the previous post).
We have touch input events coming in at every 10 milliseconds that moves by 10 pixels and a refresh display vsync event every 16.6 milliseconds. Android's algorithm, creates a new timing event called Sample Time, which is always 5 milliseconds behind the vsync event. Thus, the first sample time is at time st=11 ms (16 vsync time - 5 sample time), then the next sample time event at time st=27 ms (32 ms vsync - 5), and the next at 43 ms (48 - 5). Let's take a look at the same graph with the sample time:
The sample time is used to balance and determine whether touch events are extrapolated or interpolated. We only ever look at the last two real touch events, never at a sampled event. If the last touch event occurs AFTER the sample time, but BEFORE the vsync time, we interpolate. This occurs for example at time vsync t=32 ms. The sample time is time st=27 ms, but we have two touch events. One touch event at time t1=20 ms and time t2=30 ms. Since the last touch event, t2, is at 30 ms and after 27ms, we interpolate these two touch events. If the last touch event occurs BEFORE the sample time, we extrapolate touch events. For example, at vsync event t=48 ms, we have a sample time of st=43 ms. The last touch event is at time t=40 ms, which is before the sample time. We will use the last two touch events at time t1=30ms and t2=40ms to extrapolate the touch event for vsync event t=48. If there exists a touch event AFTER the sample time, not the vsync time, we interpolate the last two touches. If both touch events occur BEFORE the sample time, we extrapolate the last two touch events.
Interpolation
Let's take a look at the interpolation case. It is not a simple midpoint interpolation as it takes into account when the touch event occurs relative to the sample time. First, we calculate the amount of time that has passed between the two last touch events, let's call this the touch time difference. This should relatively stable per device. In our case this should always be 10 milliseconds. Next, we calculate the time difference between the sample time and the touch event that is BEFORE the sample time (touch sample diff). For our example at vsync t=32, the sample time is 27ms. The first touch event that is before the sample time is at t=20ms. Thus, 27 ms sample time - 20 ms touch time = 7ms. Next, we create a variable called alpha that is the touch sample difference / touch time difference. In this case, 7 ms / 10 ms = 0.7. Finally, we do linear interpolation with this alpha value as the midpoint modifier between the touch event after the sample time and the touch event prior to the sample time. Our two touch events were at time t=20, displacement d=20 and t=30 with a displacement of d=30. We start by using the first touch event before the sample and add an interpolated displacement to it. Thus, we have an interpolated displacement d=20 + (30 - 20) * alpha, which is 20 + (10 * 0.7) = 27. Thus at vsync time t=32, we send a touch event with a displacement of d=27. A larger alpha means we lean more towards the last touch event and a lower alpha means we lean more towards the first touch event. Here it is in equation form:
Here is the general equation. The LastTouch refers to the touch ahead of the SampleTime. The FirstTouch refers to the touch before the SampleTime.
Let's take a look at another example, at vsync time t=80. We have two touch events, one at time t=70 and another at time t=80. Our sample time here is 80 ms - 5 = 75 ms. Since we have one touch event t=80 that occurs after the sample time we interpolate. Here is the work:
We see that we have a final result of displacement d=75. That's it for interpolation.
Extrapolation
Touch extrapolation occurs when the last touch event occurs BEFORE the sample time. This occurs at vsync time t=48. Our sample time here is 48 - 5 = 43 ms. We have two touch events one at time t=30 and another at time t=40 ms. Since both are before 43 ms, we extrapolate the touch events. The logic works similarly to the touch interpolation with a few differences. We still have the same touch time difference between the two touch events which is always 10 ms. Next, we calculate the touch sample difference, which is now the last touch event minus the sample time, thus we expect a negative number. Thus we take the last touch event t=40 - the sample time st=43 = -3. Next we calculate alpha the same way which is touch sample difference / touch time difference. This case it is (-3 / 10) = -0.3. Finally we again use the same linear interpolation equation, but because alpha is negative we will extrapolate. In addition, we swap the operands and subtract the first touch from the last touch and set the starting displacement to be the last touch. Thus unlike the interpolation algorithm, we start with the last touch event and add a displacement to that. Our final result is displacement d=40 + (30 - 40) * -0.3 = 43. Thus we extrapolated 3 pixels in this case. Here's all the math:
Here is the general extrapolation equation. The Last Touch refers to the most recent touch. First touch refers to the earlier touch event. We still use the last two touch events to extrapolate.
Let's do one more extrapolation case at vsync time t=128 ms. Here is the work for a final displacement of d=123ms.
Here is the final displacement figures if we do interpolation and extrapolation across our original input:
Wow. Just wow. Outside of the first frame because we have no extra touch events, it hits the ideal case of moving a displacement of 16 pixels every 16 milliseconds for a perfect smooth scroll. It has a Frame Uniformity standard deviation of 0. What's even more amazing is that these formulas to calculate touch interpolation and extrapolation works across different touch screen refresh rates. For example, Mozilla's Flame reference device has a touch refresh rate of every 13 ms instead of every 10 ms like the Nexus 4 and it still works to create a perfect smooth scroll. Even more amazing, this algorithm accounts for touch driver noise because real devices don't send a touch event at exactly perfect 10 ms intervals, they jitter so you get touch events at 9.9ms or 10.5ms.
How does it feel in real life? Since we actually extrapolate touch events, if we're scrolling, it feels more responsive since it seems to keep up with your finger better. In addition, flings feel faster making the whole system feel not necessarily smoother but more responsive. While tracking your finger, or doing a slow scroll, we get the additional benefit that scrolling feels smoother as well. In all aspects, compared to the other touch algorithms, this is superior. On fast scrolls it keeps up with your finger better than the previous sampling algorithms. On slow scrolls, it smooths out the touch events creating a smooth experience. The only downside is that if you change your fingers direction, it will be a bit more jarring if we extrapolate then change directions. However, in real life I only barelynoticed it rarely and only because I was looking for it. Overall, a very nice win.